package sort.leetcode_912;

public class HeapSort {
    public int[] sortArray(int[] nums) {
        if(nums.length == 1){
            return nums;
        }
        heapSort(nums);
        return nums;
    }
    public void heapSort(int[] nums){
        //调成最大堆
        int len = nums.length;
        for(int i = (len - 2) / 2; i >= 0; i--){
            downAdjust(nums, i, len);
        }
        //循环交换堆顶
        for(int i = len - 1; i > 0; i--){
            swap(nums, 0, i);
            downAdjust(nums, 0, i);
        }
    }
    public void downAdjust(int[] nums, int parentIndex, int size){
        int childIndex = parentIndex * 2 + 1;
        while(childIndex < size){
            if(childIndex + 1 < size && nums[childIndex + 1] > nums[childIndex]){
                childIndex++;
            }
            if(nums[parentIndex] > nums[childIndex]){
                break;
            }
            swap(nums, parentIndex, childIndex);
            parentIndex = childIndex;
            childIndex = parentIndex * 2 + 1;
        }
    }
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
